package leetcode

//https://leetcode.com/problems/substring-with-concatenation-of-all-words/
fun main(args: Array<String>) {
//
//    val list = listOf("aaa", "bbb", "aaa")
//
//
//    val set1 = hashSetOf<List<String>>(list.sorted())
//
//    val element = listOf("aaa", "aaa", "bbb")
//
//
//    if (set1.contains(element.sorted())) println("ccc")
//    else println("nnnn")

    //"lingmindraboofooowingdingbarrwingmonkeypoundcake"
    //["fooo","barr","wing","ding","wing"]

    //sfoobarteeeeeeebarfoosss
    //"foo", "bar"
    println(findSubstringVersion1("sfoobarteeeeeeebarfoosss", arrayOf("foo", "bar")))
}

/**
 * 按照word的长度一组一组的找
 */
//todo 972 ms 18.75%
fun findSubstring(s: String, words: Array<String>): List<Int> {

    if (words.isEmpty() || s.isEmpty()) return listOf()

    val result = arrayListOf<Int>()
    val wordLen = words[0].length
    val size = words.size
    val wordSet = hashSetOf(words.asList().sorted())

    var i = 0

    while (i <= s.length - size * wordLen) {
        val list = arrayListOf<String>()
        var k = 0
        while (k < size) {
            val startIndex = i + k * wordLen
            if (startIndex < s.length && startIndex + wordLen <= s.length) {
                val element = s.substring(startIndex, startIndex + wordLen)
                list.add(element)
                k++

            } else {
                return result
            }
        }

        if (wordSet.contains(list.sorted()))
            result.add(i)

        i += wordLen
    }
    return result
}

//第一次改进：sliding Window
fun findSubstringVersion1(s: String, words: Array<String>): List<Int> {

    if (words.isEmpty() || s.isEmpty()) return listOf()

    val result = arrayListOf<Int>()

    val table = Array(128) { 0 }
    val sTable = Array(128) { 0 }
    var formed = 0
    var required = 0
    words.forEach {
        it.forEach {
            table[it.toInt()]++
            required++
        }
    }


    var i = 0
    while (i < s.length) {
        val index = s[i].toInt()
        val count = table[index]
        sTable[index]++
        if (count != 0) {
            if (sTable[index] <= count)
                formed++
        } else {//并不在目标字母中，跳过
            i++
            formed = 0
            continue
        }

        if (formed == required)
            result.add(i - required + 1)
        i++
    }
    return result
}